//B+树
#ifndef __BPLUSTREE__HPP
#define __BPLUSTREE__HPP

#include"BTree.hpp"

namespace NgSiuKei {

//重新链接叶节点
template<class TheClass>
static void relinkLeafNode(b_tree_node<TheClass> *&tree) {
    U_L_L leafNodeNum = getLeafNodeNum(tree);
    b_tree_node<TheClass> **leafNodes = getAllLeafNode(tree);
    for(U_L_L i=0; i<leafNodeNum-1; ++i) {
        leafNodes[i]->nextOne = leafNodes[i+1];
    }
    leafNodes[leafNodeNum-1]->nextOne = nullptr;
    delete []leafNodes;
}

//拆分树节点
template<class TheClass>
static void resolveBPlusTreeNode(b_tree_node<TheClass> *&tree) {
    if(nullptr == tree || tree->valNum != tree->m) {
        return;
    }

    U_L_L i;
    U_L_L index = (tree->m/2)-((0==tree->m%2)?(1):(0));//中间节点下标
    if(nullptr == tree->childs[0]) {//B+树的叶节点拆分和B树不同
        index = tree->m/2;
    }

    //中间值
    TheClass centerVal = tree->vals[index];

    //创建拆分后的大一点的新节点
    U_L_L biggerNodeValsNum = tree->m-index-((nullptr==tree->childs[0])?(0):(1));
    TheClass *dataBigger = new TheClass[biggerNodeValsNum];
    for(i=0; i<biggerNodeValsNum; ++i) {
        dataBigger[i] = tree->vals[index+i+((nullptr==tree->childs[0])?(0):(1))];
    }
    b_tree_node<TheClass> *biggerNode = cerateBTreeNode(dataBigger[0], tree->m);
    biggerNode->valNum = biggerNodeValsNum;
    for(i=1; i<biggerNodeValsNum; ++i) {
        biggerNode->vals[i] = dataBigger[i];
    }
    if(nullptr != tree->childs[0]) {
        for(i=0; i<biggerNodeValsNum+1; ++i) {
            biggerNode->childs[i] = tree->childs[index+i+1];
        }
    }

    //tree变成小一点的那个节点，删除数值、子树
    for(i=0; i<tree->valNum-index; ++i) {
        tree->childs[i+index+1] = nullptr;
    }
    tree->valNum = index;//数据数量变小就相当于删除数据

    if(nullptr == tree->parent) {
        //被拆分的是根节点，需要创建新的根节点
        b_tree_node<TheClass> *newRootNode = cerateBTreeNode(centerVal, tree->m);

        //父节点塞入新节点，新节点引用父节点
        newRootNode->childs[0] = tree;
        newRootNode->childs[1] = biggerNode;
        tree->parent = newRootNode;
        biggerNode->parent = newRootNode;
        //B+树的叶子节点相连
        if(nullptr == tree->childs[0]) {
            biggerNode->nextOne = tree->nextOne;
            tree->nextOne = biggerNode;
        }

        //tree指向新根节点
        tree = newRootNode;

        //重新设置所有节点父属性
        setAllNodeParent(tree);
    }
    else {
        //定位中间值应该塞入的位置
        U_L_L centerValIndex = 0;
        for(i=0; i<tree->parent->valNum; ++i) {
            if(centerVal < tree->parent->vals[i]) {
                centerValIndex = i;
                break;
            }
            else if(tree->parent->valNum-1 == i) {
                centerValIndex = tree->parent->valNum;
                break;
            }
        }

        //父节点值后移
        for(i=tree->parent->valNum; i>centerValIndex; --i) {
            tree->parent->vals[i] = tree->parent->vals[i-1];
        }
        //父节点子树后移
        for(i=tree->parent->valNum+1; i>centerValIndex+1; --i) {
            tree->parent->childs[i] = tree->parent->childs[i-1];
        }

        //父节点塞入中间值
        tree->parent->vals[centerValIndex] = centerVal;
        tree->parent->valNum++;

        //父节点塞入新节点，新节点引用父节点
        tree->parent->childs[centerValIndex+1] = biggerNode;
        biggerNode->parent = tree->parent;

        //B+树的叶子节点相连
        if(nullptr == tree->childs[0]) {
            biggerNode->nextOne = tree->nextOne;
            tree->nextOne = biggerNode;
        }

        //重新设置所有节点父属性
        setAllNodeParent(tree->parent, tree->parent->parent);

        //若父节点被添加中间值后满了了，就拆分父节点
        if(tree->parent->m == tree->parent->valNum) {
            resolveBTreeNode(tree->parent);
        }
    }

    delete []dataBigger;
}

//插入值
template<class TheClass>
void insertValIntoBPlusTree(b_tree_node<TheClass> *&tree, TheClass val) {
    if(nullptr == tree) {
        return;
    }

    if(nullptr == tree->childs[0]) {
        //叶子结点
        tree->vals[tree->valNum] = val;
        tree->valNum++;
        bubbleSort(tree->vals, tree->valNum);

        if(tree->m == tree->valNum) {
            //满了，需要拆分节点
            resolveBPlusTreeNode(tree);//B+树与B树的拆分方式有点不同
        }
    }
    else {
        //非叶子节点，爬树
        for(U_L_L i=0; i<tree->valNum; ++i) {
            if(val == tree->vals[i]) {
                return;
            }
            else if(val < tree->vals[i]) {
                insertValIntoBPlusTree(tree->childs[i], val);
                return;
            }
            else if(i == tree->valNum-1) {
                insertValIntoBPlusTree(tree->childs[tree->valNum], val);
                return;
            }
        }
    }
}

//删除值
template<class TheClass>
bool deleteValFromBPlusTree(b_tree_node<TheClass> *&tree, TheClass val) {
    if(nullptr == tree || !findValInBTree(tree, val)) {
        return false;
    }

    /*
    B+树删除有几种情况：
    1、找到包含关键值的结点，如果关键字个数大于⌈m/2⌉-1，直接删除即可;
    2、找到包含关键值的结点,如果关键字个数大于⌈m/2⌉-1，并且关键值是当前节点的最大(小)值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。
    3、找到包含关键值的结点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟结点有多余的关键字，则从其兄弟结点借用关键字
    4、找到包含关键值的结点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟结点没有多余的关键字，则与兄弟结点合并。
    */
    
    bool result = false;
    U_L_L childIndex;
    for(U_L_L i=0; i<tree->valNum; ++i) {
        if(val < tree->vals[i]) {
            childIndex = i;
            break;
        }
        else if(val == tree->vals[i]) {
            if(nullptr == tree->childs[0]) {//叶节点
                //直接删除就行了
                for(U_L_L j=i; j<tree->valNum-1; ++j) {
                    tree->vals[j] = tree->vals[j+1];
                }
                --tree->valNum;
                return true;
            }
            else {//非叶节点
                childIndex = i+1;
                break;
            }
        }
        else if(i == tree->valNum-1) {
            childIndex = tree->valNum;
            break;
        }
    }
    //获取目标值所在的子树
    b_tree_node<TheClass> *child = tree->childs[childIndex];
    result = deleteValFromBPlusTree(child, val);

    //如果删除过数据，要根据特定情况做调整
    if(result) {
        if(!isRich(child->valNum, child->m)) {
            //获取左右子节点
            b_tree_node<TheClass> *leftChild = nullptr;
            b_tree_node<TheClass> *rightChild = nullptr;
            if(childIndex > 0) {
                leftChild = tree->childs[childIndex-1];
            }
            if(childIndex < tree->valNum) {
                rightChild = tree->childs[childIndex+1];
            }
            //特殊操作
            if(nullptr != leftChild && isRich(leftChild->valNum-1, leftChild->m)) {//向左节点拿值
                //值后移
                for(U_L_L i=child->valNum; i>0; --i) {
                    child->vals[i] = child->vals[i-1];
                }
                //子节点后移
                for(U_L_L i=child->valNum+1; i>0; --i) {
                    child->childs[i] = child->childs[i-1];
                }
                //拿值与子节点
                if(nullptr != child->childs[1]) {
                    child->vals[0] = getMinVal(child->childs[1]);
                }
                else {
                    child->vals[0] = leftChild->vals[leftChild->valNum-1];
                }
                child->childs[0] = leftChild->childs[leftChild->valNum];
                leftChild->childs[leftChild->valNum] = nullptr;
                --leftChild->valNum;
                ++child->valNum;
                //目标值位置更新值
                tree->vals[childIndex-1] = getMinVal(child);
            }
            else if(nullptr != rightChild && isRich(rightChild->valNum-1, rightChild->m)) {//向右节点拿值
                //拿值与子节点
                child->childs[child->valNum+1] = rightChild->childs[0];
                if(nullptr != child->childs[child->valNum+1]) {
                    child->vals[child->valNum] = getMinVal(child->childs[child->valNum+1]);
                }
                else {
                    child->vals[child->valNum] = rightChild->vals[0];
                }
                ++child->valNum;
                --rightChild->valNum;
                //右节点值左移
                for(U_L_L i=0; i<rightChild->valNum; ++i) {
                    rightChild->vals[i] = rightChild->vals[i+1];
                }
                //右节点子节点左移
                for(U_L_L i=0; i<=rightChild->valNum; ++i) {
                    rightChild->childs[i] = rightChild->childs[i+1];
                }
                //目标值位置更新值
                tree->vals[childIndex] = getMinVal(tree->childs[childIndex]);
            }
            else {//合并子节点，默认合并左节点
                //定位左右节点与中间值下标
                U_L_L centerIndex = childIndex;
                if(nullptr == leftChild) {
                    leftChild = child;
                    centerIndex = childIndex;
                }
                else {
                    rightChild = child;
                    centerIndex = childIndex-1;
                }
                //合并操作
                if(nullptr != rightChild->childs[0]) {
                    leftChild->vals[leftChild->valNum] = getMinVal(rightChild->childs[0]);
                    ++leftChild->valNum;
                }
                for(U_L_L i=0; i<rightChild->valNum; ++i) {
                    leftChild->vals[leftChild->valNum+i] = rightChild->vals[i];
                }
                for(U_L_L i=0; i<=rightChild->valNum; ++i) {
                    leftChild->childs[leftChild->valNum+i] = rightChild->childs[i];
                }
                leftChild->valNum += rightChild->valNum;
                deleteBTree(rightChild, false);
                --tree->valNum;
                //值左移
                for(U_L_L i=centerIndex; i<tree->valNum; ++i) {
                    tree->vals[i] = tree->vals[i+1];
                }
                //子节点左移
                for(U_L_L i=centerIndex+1; i<tree->valNum; ++i) {
                    tree->childs[i] = tree->childs[i+1];
                }
                tree->childs[tree->valNum+1] = nullptr;
                //目标值位置更新值
                if(centerIndex > 0 && nullptr != tree->childs[centerIndex]) {
                    tree->vals[centerIndex-1] = getMinVal(tree->childs[centerIndex]);
                }
                //如果合并后的节点满阶了，要拆分节点
                if(leftChild->valNum == leftChild->m) {
                    resolveBPlusTreeNode(leftChild);
                }
                if(0 == tree->valNum && nullptr == tree->parent) {
                    b_tree_node<TheClass> *emptyNode = tree;
                    tree = tree->childs[0];
                    deleteBTree(emptyNode, false);
                }
            }
        }
        else if(0 != childIndex) {
            tree->vals[childIndex-1] = getMinVal(tree->childs[childIndex]);
        }

        //重新设置所有节点父属性
        setAllNodeParent(tree, tree->parent);

        //叶节点重新链接
        relinkLeafNode(tree);
    }

    return result;
}

//创建
template<class TheClass>
b_tree_node<TheClass> *createBPlusTree(TheClass *data, U_L_L dataSize, const U_L_L m) {
    if(nullptr == data && m < 3) {
        return nullptr;
    }

    b_tree_node<TheClass> *tree = cerateBTreeNode(data[0], m);
    for(U_L_L i=1; i<dataSize; ++i) {
        while(nullptr != tree->parent) {
            tree = tree->parent;
        }
        insertValIntoBPlusTree(tree, data[i]);
    }

    while(nullptr != tree->parent) {
        tree = tree->parent;
    }

    return tree;
}

//根据B+树特性打印
template<class TheClass>
void printBPlusTree(b_tree_node<TheClass> *tree) {
    printBTree(tree);
    while(nullptr != tree->childs[0]) {
        tree = tree->childs[0];
    }
    cout << "B+树：[ ";
    while(nullptr != tree) {
        for(U_L_L i=0; i<tree->valNum; ++i) {
            cout << tree->vals[i] << ' ';
        }
        tree = tree->nextOne;
    }
    cout << ']' << endl;
}

}

#endif